
#并查集

class UnionFind:

    def __init__(self, n):
        self.up_bound = list(range(n)) #即 self.parent
        self.rank = [0] * n # rank[i] 表示以 i 为根的树的层数(深度)

    def find(self, p):
        if self.up_bound[p] == p:
            return p
        # 递归实现路径压缩
        self.up_bound[p] = self.find(self.up_bound[p])
        return self.up_bound[p]

    def union(self, p, q):
        """
        合并p,q所在树
        """
        x = self.find(p)
        y = self.find(q)
        if x == y:       # 如果p,q已经在同一颗树，那么合并失败
            return False
        # 根据两个元素所在树的rank不同判断合并方向
        # 将rank低的集合合并到rank高的集合上(merge)
        if self.rank[x] == self.rank[y]:
            # 想象两个点（rank 1）的合并，肯定结果是一个是另个一个的孩子
            # 所以rank会加1
            self.rank[x] += 1
            self.up_bound[y] = x
        elif self.rank[x] > self.rank[y]:
            self.up_bound[y] = x
        else:
            self.up_bound[x] = y
        return True
